package MyParser;

import bit.minisys.minicc.MiniCCCfg;
import bit.minisys.minicc.internal.util.MiniCCUtil;
import bit.minisys.minicc.parser.IMiniCCParser;
import bit.minisys.minicc.parser.ast.*;
import com.fasterxml.jackson.databind.ObjectMapper;
import org.antlr.v4.gui.TreeViewer;

import java.io.File;
import java.util.ArrayList;
import java.util.Arrays;


public class ParserAnalysis implements IMiniCCParser {
    class ScannerToken{
        public String lexme;
        public String type;
        public int	  line;
        public int    column;
    }

    private ArrayList<ScannerToken> tknList;
    private int tokenIndex;
    private ScannerToken nextToken;

    private ArrayList<String> typeKeys;
    private ArrayList<String> constant;
    private ArrayList<String> Identifier;
    private ArrayList<String> stringLiteral;
    private ArrayList<String> pointer;
    private ArrayList<String> assignmentOperator;
    private ArrayList<String> unaryPrefix;
    private ArrayList<String> unaryOperator;
    private ArrayList<String> returnKey;
    private ArrayList<String> conditionKeys;
    private ArrayList<String> jumpKeys;
    private ArrayList<String> iterationKeys;

    private void initKeyWordsList() //方便查询的关键字
    {
        typeKeys = new ArrayList<>();
        typeKeys.add("'int'");
        typeKeys.add("'void'");
        typeKeys.add("'float'");
        typeKeys.add("'double'");
        typeKeys.add("'char'");
        typeKeys.add("'long'");
        typeKeys.add("'unsigned'");
        typeKeys.add("'short'");

        constant = new ArrayList<>();
        constant.add("IntegerConstant");
        constant.add("FloatingConstant");
        constant.add("CharacterConstant");
        constant.add("StringLiteral");

        Identifier = new ArrayList<>();
        Identifier.add("Identifier");

        stringLiteral = new ArrayList<>();
        stringLiteral.add("StringLiteral");

        pointer = new ArrayList<>();
        pointer.add("'*'");

        unaryOperator = new ArrayList<>();
        unaryOperator.add("'&'");
        unaryOperator.add("'*'");
        unaryOperator.add("'+'");
        unaryOperator.add("'-'");
        unaryOperator.add("'!'");

        assignmentOperator = new ArrayList<>();
        assignmentOperator.add("'='");
        assignmentOperator.add("'*='");
        assignmentOperator.add("'/='");
        assignmentOperator.add("'%='");
        assignmentOperator.add("'+='");
        assignmentOperator.add("'-='");
        assignmentOperator.add("'<<='");
        assignmentOperator.add("'>>='");
        assignmentOperator.add("'&='");
        assignmentOperator.add("'^='");
        assignmentOperator.add("'|='");

        unaryPrefix = new ArrayList<>();
        unaryPrefix.add("'++'");
        unaryPrefix.add("'--'");
        unaryPrefix.add("'Sizeof'");
        unaryPrefix.add("'sizeof'");
        unaryPrefix.addAll(unaryOperator);


        returnKey = new ArrayList<>();
        returnKey.add("'return'");

        conditionKeys = new ArrayList<>();
        conditionKeys.add("'if'");

        iterationKeys = new ArrayList<>();
        iterationKeys.add("'for'");
        iterationKeys.add("'while'");

        jumpKeys = new ArrayList<>();
        jumpKeys.add("'continue'");
        jumpKeys.add("'break'");
        jumpKeys.add("'goto'");

    }


    @Override
    public String run(String iFile) throws Exception {
        System.out.println("Parsing...");
        initKeyWordsList();
        String oFile = MiniCCUtil.removeAllExt(iFile) + MiniCCCfg.MINICC_PARSER_OUTPUT_EXT;
        String tFile = MiniCCUtil.removeAllExt(iFile) + MiniCCCfg.MINICC_SCANNER_OUTPUT_EXT;

        tknList = loadTokens(tFile);
        tokenIndex = 0;

        ASTNode root = program();

        String[] dummyStrs = new String[16];
        TreeViewer viewr = new TreeViewer(Arrays.asList(dummyStrs), root);
        viewr.open();

        ObjectMapper mapper = new ObjectMapper();
        mapper.writeValue(new File(oFile), root);

        //TODO: write to file
        return null;
    }

    private ArrayList<ScannerToken> loadTokens(String tFile) {
        tknList = new ArrayList<ScannerToken>();

        ArrayList<String> tknStr = MiniCCUtil.readFile(tFile);

        for(String str: tknStr) {
            if(str.trim().length() <= 0) {
                continue;
            }

            ScannerToken st = new ScannerToken();
            //[@0,0:2='int',<'int'>,1:0]
            String[] segs;
            if(str.indexOf("<','>") > 0) {
                str = str.replace("','", "'DOT'");

                segs = str.split(",");
                segs[1] = "=','";
                segs[2] = "<','>";

            }else {
                segs = str.split(",");
            }
            st.lexme = segs[1].substring(segs[1].indexOf("'") + 1, segs[1].length()-1);
            st.type  = segs[2].substring(segs[2].indexOf("<") + 1, segs[2].length() - 1);
            String[] lc = segs[3].split(":");
            st.line = Integer.parseInt(lc[0]);
            st.column = Integer.parseInt(lc[1].replace("]", ""));

            tknList.add(st);
        }
        return tknList;
    }

        private ScannerToken getToken(int index){
            if (index < tknList.size()){
                return tknList.get(index);
            }
            return null;
        }

        public void matchToken(String type) {
            if(tokenIndex < tknList.size()) {
                ScannerToken next = tknList.get(tokenIndex);
                if(!next.type.equals(type)) {
                    System.out.println("[ERROR]Parser: unmatched token, expected = " + type + ", "
                            + "input = " + next.type);
                }
                else {
                    tokenIndex++;
                }
            }
        }


        //语法分析机器
        // program -> (globalVarDecalation | e) funcList
        private ASTNode program() {
            ASTNode program = null;
        nextToken = tknList.get(tokenIndex);
        if (!nextToken.type.equals("EOF")) {
            ASTCompilationUnit p = new ASTCompilationUnit();
            ArrayList<ASTNode> gl = globalVarDecalationCheck();
            if(gl != null) {
                p.items.addAll(gl);
            }
            ArrayList<ASTNode> fl = funcList();  //全局声明表
            if (fl != null) {
                p.items.addAll(fl);
            }
            p.children.addAll(p.items);
            program = p;
        }
        return program;
    }


    //globalVarDecalationCheck
    private ArrayList<ASTNode> globalVarDecalationCheck()
    {
        ArrayList<ASTNode> vars = new ArrayList<>();
        int orgTokenIndex = tokenIndex;

        nextToken = tknList.get(tokenIndex);
        if(typeKeys.contains(nextToken.type)) {
            ArrayList<ASTToken> sps = typeSpecifiers();

            ASTIdentifier id = identifier();

            nextToken = tknList.get(tokenIndex);
            if(nextToken.type.equals("'('")) //函数
            {
                tokenIndex = orgTokenIndex;
                return null;
            }
            else {
                tokenIndex = orgTokenIndex;
                ASTDeclaration var = localDeclaration();
                matchToken("';'");
                vars.add(var);
                ArrayList<ASTNode> continueVars = globalVarDecalationCheck();
                if(continueVars != null)
                    vars.addAll(continueVars);
            }
        }
        return vars;
    }

    // funcList -> func funcList | e
    private ArrayList<ASTNode> funcList()
    {
        ArrayList<ASTNode> flist = new ArrayList<>();
        nextToken = tknList.get(tokenIndex);

        // e
        if(nextToken.type.equals("EOF"))
            return null;
        else{
            ASTNode node = func();
            if(node != null)
                flist.add(node);
            ArrayList<ASTNode> fl2 = funcList();
            if(fl2 != null) {
                flist.addAll(fl2);
            }
            return flist;
        }
    }

    //func -> typeSpecifier funcDeclaration blockStatement
    private ASTFunctionDefine func()
    {
        ASTFunctionDefine funcDef = new ASTFunctionDefine();
        ArrayList<ASTToken> tokens = typeSpecifiers();

        ASTFunctionDeclarator funcDeclarator = funcDeclaration();

        matchToken("'{'");
        ASTCompoundStatement cs = compoundStatement();
        matchToken("'}'");


        funcDef.specifiers.addAll(tokens);
        funcDef.children.addAll(tokens);
        funcDef.declarator = funcDeclarator;
        funcDef.children.add(funcDeclarator);
        funcDef.body = cs;
        funcDef.children.add(cs);

        return funcDef;
    }

    //funcDeclaration -> Identifier '(' arguments ')'
    private ASTFunctionDeclarator funcDeclaration() //函数申明，标识符，参数列表组成
    {
        ASTFunctionDeclarator funcDeclarator = new ASTFunctionDeclarator();

        ASTIdentifier id = identifier();
        ASTVariableDeclarator varDeclarator = new ASTVariableDeclarator();
        varDeclarator.identifier = id;
        varDeclarator.children.add(id);
        funcDeclarator.declarator = varDeclarator;
        funcDeclarator.children.add(varDeclarator);
        matchToken("'('");
        nextToken = tknList.get(tokenIndex);
        if(!nextToken.type.equals("')'")) {
            ArrayList<ASTParamsDeclarator> params = arguments();
            funcDeclarator.params = params;
            funcDeclarator.children.addAll(params);
        }
        matchToken("')'");
        return funcDeclarator;
    }

    //arguments -> argList | e
    private ArrayList<ASTParamsDeclarator> arguments()
    {
        nextToken = tknList.get(tokenIndex);
        if(nextToken.type.equals("')'"))
            return null;
        else
        {
            ArrayList<ASTParamsDeclarator> al = argList();
            return al;
        }
    }

    //argList -> arg ',' argList | arg
    private ArrayList<ASTParamsDeclarator> argList()
    {
        ArrayList<ASTParamsDeclarator> pdl = new ArrayList<>();
        ASTParamsDeclarator argDeclarator = argDeclarator();    //至少有一个参数
        pdl.add(argDeclarator);
        nextToken = tknList.get(tokenIndex);    //LL1，如果下一个是','，就用argList替代
        if(nextToken.type.equals("','"))
        {
            matchToken("','");
            pdl.addAll(argList());
        }
        return pdl;
    }

    //argDeclarator -> specifiers Identifier
    private ASTParamsDeclarator argDeclarator()
    {
        ASTParamsDeclarator argd = new ASTParamsDeclarator();

        ArrayList<ASTToken> tokens = typeSpecifiers();
        ASTVariableDeclarator vard = new ASTVariableDeclarator();
        ASTIdentifier id = identifier();
        vard.identifier = id;
        vard.children.add(id);

        argd.specfiers.addAll(tokens);
        argd.children.addAll(tokens);
        argd.declarator = vard;
        argd.children.add(vard);

        return argd;
    }

    //compoundStatement -> statementList
    private ASTCompoundStatement compoundStatement()
    {
        ASTCompoundStatement cs = new ASTCompoundStatement();
        ArrayList<ASTNode> nodes = statementList();
        if(nodes != null) {
            cs.blockItems.addAll(nodes);
            cs.children.addAll(nodes);
        }
        return cs;
    }

    //statementList -> statement statementList | statement
    private ArrayList<ASTNode> statementList()
    {
        ArrayList<ASTNode> statements = new ArrayList<>();
        nextToken = tknList.get(tokenIndex);
        if(nextToken.type.equals("'}'"))
            return null;
        else
        {
            ASTNode statement = statement();
            if(statement != null)
                statements.add(statement);

            ArrayList<ASTNode> statListNode = statementList();
            if(statListNode != null)
                statements.addAll(statListNode);
        }
        return statements;
    }

    //statement -> declarationStatement | expressionStatement | returnStatement  | selectionStatement | compoundStatement | jumpStatement | emptyStatement
    private ASTNode statement()
    {
        ASTNode retStat = null;
        nextToken = tknList.get(tokenIndex);    //这里需要向下看一个，判断进入哪一个子程序
        if(typeKeys.contains(nextToken.type))    //以typeKeys开头的语句一定是声明
        {
            ASTDeclaration statDec = localDeclaration();    //局部变量申明
            retStat = statDec;
            matchToken("';'");
        }
        else if(Identifier.contains(nextToken.type) || unaryPrefix.contains(nextToken.type))    //Identifier 或者 一元运算符开头是表达式
        {
            ASTExpressionStatement expressionStatement = expressionStatement();
            matchToken("';'");
            retStat = expressionStatement;
        }
        else if(returnKey.contains(nextToken.type)) //return statement
        {
            ASTReturnStatement returnStatement = returnStatement();
            matchToken("';'");
            retStat = returnStatement;
        }
        else if(conditionKeys.contains(nextToken.type)) //selectionStatement
        {
            ASTSelectionStatement selectionStatement = selectionStatement();
            retStat = selectionStatement;
        }
        else if(nextToken.type.equals("'{'"))   //compoundStatement
        {
            matchToken("'{'");
            ASTCompoundStatement compoundStatement = compoundStatement();
            matchToken("'}'");
            retStat = compoundStatement;
        }
        else if(jumpKeys.contains(nextToken.type))  //jumpStatement
        {
            ASTStatement jumpStat = jumpStatement();
            matchToken("';'");
            retStat = jumpStat;
        }
        else if(iterationKeys.contains(nextToken.type)) //iterationStatement
        {
            ASTStatement iterationStatement = iterationStatement();
            retStat = iterationStatement;
        }
        else if(nextToken.type.equals("';'"))
        {
            matchToken("';'");
            retStat = null;
        }
        return retStat;
    }

    //localDeclaration -> typeKeys declarationInitLists
    private ASTDeclaration localDeclaration()
    {
        ASTDeclaration statDec = new ASTDeclaration();
        //specifier
        nextToken = tknList.get(tokenIndex);
        ArrayList<ASTToken> sps = typeSpecifiers();

        statDec.specifiers.addAll(sps);
        statDec.children.addAll(sps);

        //InitLists
        ArrayList<ASTInitList> arrayList = declarationInitLists();
        statDec.initLists.addAll(arrayList);
        statDec.children.addAll(arrayList);

        return statDec;
    }

    //declarationInitLists -> declarationInitList ',' declarationInitLists | declarationInitList
    private ArrayList<ASTInitList> declarationInitLists()
    {
        ArrayList<ASTInitList> arrayList = new ArrayList<>();
        ASTInitList initList = declarationInitList();
        arrayList.add(initList);

        nextToken = tknList.get(tokenIndex);
        if(nextToken.type.equals("','"))   //如果是逗号，使用第一个候选式
        {
            matchToken("','");
            arrayList.addAll(declarationInitLists());
        }
        return arrayList;
    }


    //declarationInitList -> declarator | declarator '=' assignmentExpressions
    private ASTInitList declarationInitList()
    {
        ASTInitList initList = new ASTInitList();
        ASTDeclarator declarator = localDeclarator();
        initList.declarator = declarator;
        initList.children.add(declarator);

        nextToken = tknList.get(tokenIndex);
        if(nextToken.type.equals("'='"))
        {
            matchToken("'='");

            nextToken = tknList.get(tokenIndex);
            if(nextToken.type.equals("'{'"))    //数组初始化
            {
                matchToken("'{'");
                ArrayList<ASTExpression> exprs = expressionList();
                if(exprs != null)
                {
                    initList.exprs.addAll(exprs);
                    initList.children.addAll(exprs);
                }
                matchToken("'}'");

            }
            else
            {
                ASTExpression expression = assignmentExpression();  //只能是赋值表达式
                if(expression != null) {
                    initList.exprs.add(expression);
                    initList.children.add(expression);
                }
            }

        }
        return initList;
    }

    //localDeclarator -> VarDeclarator | VarDeclarator arrays
    private ASTDeclarator localDeclarator()
    {
        ASTIdentifier id = identifier();
        ASTDeclarator retDec = null;
        nextToken = tknList.get(tokenIndex);
        if(nextToken.type.equals("'['"))       //数组申明
        {
            ASTVariableDeclarator variableDeclarator = new ASTVariableDeclarator();
            variableDeclarator.identifier = id;
            variableDeclarator.children.add(id);
            ASTDeclarator parentDeclarator = arrayDeclarator(variableDeclarator);
            retDec = parentDeclarator;
        }
        else
        {
            ASTVariableDeclarator declarator = new ASTVariableDeclarator();
            declarator.identifier = id;
            declarator.children.add(id);
            retDec = declarator;
        }
        return retDec;
    }

    //arrayDeclarator
    private ASTDeclarator arrayDeclarator(ASTDeclarator childDeclarator)
    {
        nextToken = tknList.get(tokenIndex);
        if(nextToken.type.equals("'['")) {
            ASTArrayDeclarator arrayDeclarator = new ASTArrayDeclarator();
            matchToken("'['");
            arrayDeclarator.declarator = childDeclarator;
            arrayDeclarator.children.add(childDeclarator);
            ASTExpression expression = expression();
            arrayDeclarator.expr = expression;
            arrayDeclarator.children.add(expression);
            matchToken("']'");
            return arrayDeclarator(arrayDeclarator);
        }
        else
            return childDeclarator;
    }



    //expression part
    //expressionStatement -> expression ';'
    private ASTExpressionStatement expressionStatement()
    {
        ASTExpressionStatement expressionStatement = new ASTExpressionStatement();
        //ASTExpression expression = expression();
        ASTExpression expression = expression();
        if(expression != null)
        {
            expressionStatement.exprs.add(expression);
            expressionStatement.children.add(expression);
        }
        return expressionStatement;
    }


    //用逗号作为分隔符而不是运算符号的特殊表达式表
    private ArrayList<ASTExpression> expressionList()
    {
        ArrayList<ASTExpression> expressionList = new ArrayList<>();
        ASTExpression expression = assignmentExpression();
        expressionList.add(expression);

        nextToken = tknList.get(tokenIndex);
        if(nextToken.type.equals("','"))
        {
            matchToken("','");
            ArrayList<ASTExpression> expressions = expressionList();
            if(expressions != null)
            {
                expressionList.addAll(expressions);
            }
        }

        return expressionList;
    }



    //expression -> expression ',' assignmentExpression | assignmentExpression
    //消除左递归
    //expression -> assignmentExpression expressionSub
    //expressionSub -> ',' assignmentExpression expressionSub | e
    private ASTExpression expression()
    {
        ASTExpression retExpression  = null;    //实际的返回值
        ASTExpression assignmentExpression = assignmentExpression();
        ASTExpression subExpression = expressionSub(assignmentExpression);
        if(subExpression != null)   //返回为null意味着没有，运算符构成的二元表达式，直接返回赋值表达式即可
        {
            retExpression = subExpression;
        }
        else
        {
            retExpression = assignmentExpression;
        }
        return retExpression;
    }
    private ASTExpression expressionSub(ASTExpression preExpression)  //消除左递归
    {
        ASTExpression retExpression = null;
        nextToken = tknList.get(tokenIndex);
        if(nextToken.type.equals("','"))
        {
            ASTBinaryExpression dotBinaryExpression = new ASTBinaryExpression();
            dotBinaryExpression.expr1 = preExpression;  //expr1
            dotBinaryExpression.children.add(preExpression);
            ASTToken token = transformNextToken();
            dotBinaryExpression.op = token; //逗号运算符
            dotBinaryExpression.children.add(token);
            ASTExpression expr2 = assignmentExpression(); //expr2
            dotBinaryExpression.expr2 =  expr2;
            dotBinaryExpression.children.add(expr2);
            ASTExpression subExpression = expressionSub(dotBinaryExpression);
            if(subExpression != null)
                retExpression = subExpression;
            else
                retExpression = dotBinaryExpression;
        }
        return retExpression;
    }

    //assignmentExpression -> conditionExpression | unaryExpression(++ | -- | id | constant | '(') assignmentOperator assignmentExpression
    //assignmentExpression -> conditionExpression assignmentOperator assignmentExpression | assignmentExpression
    private ASTExpression assignmentExpression()
    {
        ASTExpression retExpression = null;
        //ASTExpression unaryExpression = unaryExpression(null);  //先求一个
        ASTExpression conditionExpression  = conditionExpression();
        nextToken = tknList.get(tokenIndex);

        if(assignmentOperator.contains(nextToken.type)) //第二个候选式
        {
            ASTBinaryExpression assignmentExpression = new ASTBinaryExpression();
            assignmentExpression.expr1 = conditionExpression;
            assignmentExpression.children.add(conditionExpression);
            ASTToken op = transformNextToken();
            assignmentExpression.op = op;
            assignmentExpression.children.add(op);

            ASTExpression expr2 = assignmentExpression();
            assignmentExpression.expr2 = expr2;
            assignmentExpression.children.add(expr2);
            retExpression = assignmentExpression;
        }
        else    //走条件表达式的路径
        {
            retExpression = conditionExpression;
        }
        return retExpression;
    }

    //conditionExpression -> logicORExpression | logical_OR_Expression '?' expression ':' conditionalExpression;
    private ASTExpression conditionExpression()
    {
        ASTExpression retExpression = null;
        ASTExpression logicaORExpression = logicORExpression();
        nextToken = tknList.get(tokenIndex);
        if(nextToken.type.equals("'?'"))    //条件表达式
        {
            ASTConditionExpression conditionExpression = new ASTConditionExpression();
            ASTExpression flagExp = logicaORExpression;
            matchToken("'?'");
            ASTExpression trueExpression = expression();
            matchToken("':'");
            ASTExpression falseExpression = conditionExpression();

            conditionExpression.condExpr = flagExp;
            conditionExpression.children.add(flagExp);
            conditionExpression.trueExpr.add(trueExpression);
            conditionExpression.children.add(trueExpression);
            conditionExpression.falseExpr = falseExpression;
            conditionExpression.children.add(falseExpression);

            retExpression = conditionExpression;
        }
        else    //逻辑或表达式
        {
            retExpression = logicaORExpression;
        }

        return retExpression;
    }

    //logicORExpression -> logicANDExpression logicORExpressionSub  //消除左递归
    //logicORExpressionSub -> '||' logicalANDExpression logicORExpressionSub
    private ASTExpression logicORExpression()
    {
        ASTExpression retExpression = null;
        ASTExpression logicANDExp = logicANDExpression();
        ASTExpression subExpression = logicORExpressionSub(logicANDExp);
        if(subExpression != null)
        {
            retExpression = subExpression;
        }
        else
        {
            retExpression = logicANDExp;
        }
        return retExpression;
    }
    private ASTExpression logicORExpressionSub(ASTExpression expr1)
    {
        ASTExpression retExpression = null;
        nextToken = tknList.get(tokenIndex);
        if(nextToken.type.equals("'||'"))   //或运算
        {
            ASTBinaryExpression orExpression = new ASTBinaryExpression();
            ASTToken op = transformNextToken();

            orExpression.expr1 = expr1;
            orExpression.children.add(expr1);

            orExpression.op = op;
            orExpression.children.add(op);

            ASTExpression expr2 = logicANDExpression();
            orExpression.expr2 = expr2;
            orExpression.children.add(expr2);

            ASTExpression subExpression = logicORExpressionSub(orExpression);
            if(subExpression != null)
            {
                retExpression = subExpression;
            }
            else
                retExpression = orExpression;
        }
        return retExpression;
    }

    //logicANDExpression -> equalityExpression logicANDExpressionSub
    //logicANDExpressionSub -> '&&' equalityExpression logicANDExpressionSub
    private ASTExpression logicANDExpression()
    {
        ASTExpression retExpression = null;
        ASTExpression equalityExpression = equalityExpression();
        ASTExpression subExpression = logicANDExpressionSub(equalityExpression);
        if(subExpression != null)
        {
            retExpression = subExpression;
        }
        else
        {
            retExpression = equalityExpression;
        }
        return retExpression;
    }
    private ASTExpression logicANDExpressionSub(ASTExpression expr1)
    {
        ASTExpression retExpression = null;
        nextToken = tknList.get(tokenIndex);
        if(nextToken.type.equals("'&&'"))   //或运算
        {
            ASTBinaryExpression andExpression = new ASTBinaryExpression();
            ASTToken op = transformNextToken();

            andExpression.expr1 = expr1;
            andExpression.children.add(expr1);

            andExpression.op = op;
            andExpression.children.add(op);

            ASTExpression expr2 = equalityExpression();
            andExpression.expr2 = expr2;
            andExpression.children.add(expr2);

            ASTExpression subExpression = logicANDExpressionSub(andExpression);
            if(subExpression != null)
            {
                retExpression = subExpression;
            }
            else
            {
                retExpression = andExpression;
            }
        }
        return retExpression;
    }

    //equalityExpression -> relationExpression equalityExpressionSub
    //equalityExpressionSub -> '=='|'!=' relationExpression equalityExpreesionSub
    private ASTExpression equalityExpression()
    {
        ASTExpression retExpression = null;
        ASTExpression relationExpression = relationExpression();
        ASTExpression subExpression = equalityExpressionSub(relationExpression);
        if(subExpression != null)
        {
            retExpression = subExpression;
        }
        else
        {
            retExpression = relationExpression;
        }
        return retExpression;
    }
    private ASTExpression equalityExpressionSub(ASTExpression expr1)
    {
        ASTExpression retExpression = null;
        nextToken = tknList.get(tokenIndex);
        if(nextToken.type.equals("'=='") || nextToken.type.equals("'!='"))   //或运算
        {
            ASTBinaryExpression equalityExpression = new ASTBinaryExpression();
            ASTToken op = transformNextToken();

            equalityExpression.expr1 = expr1;
            equalityExpression.children.add(expr1);

            equalityExpression.op = op;
            equalityExpression.children.add(op);

            ASTExpression expr2 = relationExpression();
            equalityExpression.expr2 = expr2;
            equalityExpression.children.add(expr2);

            ASTExpression subExpression = equalityExpressionSub(equalityExpression);
            if(subExpression != null)
            {
                retExpression = subExpression;
            }
            else
            {
                retExpression = equalityExpression;
            }
        }
        return retExpression;
    }

    //relationExpression -> additiveExpression relationExpressionSub
    //relationExpressionSub -> '< | > | <= | >=' additiveExpression relationExpressionSub
    private ASTExpression relationExpression()
    {
        ASTExpression retExpression = null;
        ASTExpression additiveExpression = additiveExpression();
        ASTExpression subExpression = relationExpressionSub(additiveExpression);
        if(subExpression != null)
        {
            retExpression = subExpression;
        }
        else
        {
            retExpression = additiveExpression;
        }
        return retExpression;
    }
    private ASTExpression relationExpressionSub(ASTExpression expr1)
    {
        ASTExpression retExpression = null;
        nextToken = tknList.get(tokenIndex);
        if(nextToken.type.equals("'>='") || nextToken.type.equals("'<='") || nextToken.type.equals("'>'") || nextToken.type.equals("'<'"))   //关系比较
        {
            ASTBinaryExpression relationExpression = new ASTBinaryExpression();
            ASTToken op = transformNextToken();

            relationExpression.expr1 = expr1;
            relationExpression.children.add(expr1);

            relationExpression.op = op;
            relationExpression.children.add(op);

            ASTExpression expr2 = additiveExpression();
            relationExpression.expr2 = expr2;
            relationExpression.children.add(expr2);

            ASTExpression subExpression = relationExpressionSub(relationExpression);
            if(subExpression != null)
            {
                retExpression = subExpression;
            }
            else
            {
                retExpression = relationExpression;
            }
        }
        return retExpression;
    }

    //additiveExpression -> multiplicativeExpression additiveExpressionSub
    //additiveExpressionSub -> '+ | -' multiplicativeExpression additiveExpressionSub
    private ASTExpression additiveExpression()
    {
        ASTExpression retExpression = null;
        ASTExpression multiplicativeExpression = multiplicativeExpression();
        ASTExpression subExpression = additiveExpressionSub(multiplicativeExpression);
        if(subExpression != null)
        {
            retExpression = subExpression;
        }
        else
        {
            retExpression = multiplicativeExpression;
        }
        return retExpression;
    }
    private ASTExpression additiveExpressionSub(ASTExpression expr1)
    {
        ASTExpression retExpression = null;
        nextToken = tknList.get(tokenIndex);
        if(nextToken.type.equals("'+'") || nextToken.type.equals("'-'"))   //加减
        {
            ASTBinaryExpression additiveExpression = new ASTBinaryExpression();
            ASTToken op = transformNextToken();

            additiveExpression.expr1 = expr1;
            additiveExpression.children.add(expr1);

            additiveExpression.op = op;
            additiveExpression.children.add(op);

            ASTExpression expr2 = multiplicativeExpression();
            additiveExpression.expr2 = expr2;
            additiveExpression.children.add(expr2);

            ASTExpression subExpression = additiveExpressionSub(additiveExpression);
            if(subExpression != null)
            {
                retExpression = subExpression;
            }
            else
            {
                retExpression = additiveExpression;
            }
        }
        return retExpression;
    }

    //multiplicativeExpression -> castExpression multiplicativeExpressionSub
    //multiplicativeExpressionSub -> '* | / | %' castExpression multiplicativeExpressionSub
    private ASTExpression multiplicativeExpression()
    {
        ASTExpression retExpression = null;
        ASTExpression castExpression = castExpression();
        ASTExpression subExpression = multiplicativeExpressionSub(castExpression);
        if(subExpression != null)
        {
            retExpression = subExpression;
        }
        else
        {
            retExpression = castExpression;
        }
        return retExpression;
    }
    private ASTExpression multiplicativeExpressionSub(ASTExpression expr1)
    {
        ASTExpression retExpression = null;
        nextToken = tknList.get(tokenIndex);
        if(nextToken.type.equals("'*'") || nextToken.type.equals("'/'") || nextToken.type.equals("'%'"))   //乘除模
        {
            ASTBinaryExpression multiplicativeExpression = new ASTBinaryExpression();
            ASTToken op = transformNextToken();

            multiplicativeExpression.expr1 = expr1;
            multiplicativeExpression.children.add(expr1);

            multiplicativeExpression.op = op;
            multiplicativeExpression.children.add(op);

            ASTExpression expr2 = castExpression();
            multiplicativeExpression.expr2 = expr2;
            multiplicativeExpression.children.add(expr2);

            ASTExpression subExpression = multiplicativeExpressionSub(multiplicativeExpression);
            if(subExpression != null)
            {
                retExpression = subExpression;
            }
            else
            {
                retExpression = multiplicativeExpression;
            }
        }
        return retExpression;
    }

    //castExpression -> '('typeName')' expression | '(' expression ')' | unaryExpression
    private ASTExpression castExpression()
    {
        ASTExpression retExpression = null;
        nextToken = tknList.get(tokenIndex);
        if(nextToken.type.equals("'('")) {
            matchToken("'('");
            nextToken = tknList.get(tokenIndex);
            if (typeKeys.contains(nextToken.type)) {
                ASTCastExpression castExpression = new ASTCastExpression();
                ASTTypename typename = new ASTTypename();
                ASTToken sp = transformNextToken();
                typename.specfiers.add(sp);
                typename.children.add(sp);

                castExpression.typename = typename;
                castExpression.children.add(typename);

                matchToken("')'");

                ASTExpression expression = castExpression();
                castExpression.expr = expression;
                castExpression.children.add(expression);

                retExpression = castExpression;
            } else {
                ASTExpression expression = expression();
                matchToken("')'");
                retExpression = expression;
            }
        }
        else
            retExpression = unaryExpression();
        return retExpression;
    }
    //unaryExpression -> postfixExpression | '++'unaryExpression | '--' unaryExpression | unaryOperator unaryExpression
    // | 'sizeof' unaryExpression | 'sizeof' '(' castExpression ')'
    private ASTExpression unaryExpression()
    {
        ASTExpression retExpression = null;
        nextToken = tknList.get(tokenIndex);
        if(Identifier.contains(nextToken.type) || constant.contains(nextToken.type) || stringLiteral.contains(nextToken.type) || nextToken.type.equals("'('"))
        {
            ASTExpression positfixExpression = positfixExpression();
            retExpression = positfixExpression;
        }
        else if(unaryPrefix.contains(nextToken.type))
        {
            ASTUnaryExpression unaryExpression = new ASTUnaryExpression();
            ASTToken op = transformNextToken();

            unaryExpression.op = op;
            unaryExpression.children.add(op);

            if(op.value.equals("sizeof"))
            {
                matchToken("'('");
                nextToken = tknList.get(tokenIndex);
                if(typeKeys.contains(nextToken.type))  //TypeName
                {
                    ASTUnaryTypename typename = new ASTUnaryTypename();
                    typename.op = op;
                    typename.children.add(op);
                    ASTToken sp = transformNextToken();
                    ASTTypename tn = new ASTTypename();
                    tn.specfiers.add(sp);
                    tn.children.add(sp);
                    typename.typename = tn;
                    typename.children.add(tn);
                    matchToken("')'");
                    retExpression = typename;
                }
                else    //sizeof(castExpression)
                {
                    nextToken = tknList.get(tokenIndex);
                    if(!nextToken.type.equals("')'")) {
                        ASTExpression exp = expression();
                        unaryExpression.expr = exp;
                        unaryExpression.children.add(exp);
                    }
                    matchToken("')'");
                    retExpression = unaryExpression;
                }
            }
            else
            {
                nextToken = tknList.get(tokenIndex);
                if(!unaryOperator.contains(nextToken.type)) {
                    ASTExpression exp = unaryExpression();
                    unaryExpression.expr = exp;
                    unaryExpression.children.add(exp);
                    retExpression = unaryExpression;
                }
                else
                {
                    ASTExpression exp = castExpression();
                    unaryExpression.expr = exp;
                    unaryExpression.children.add(exp);
                    retExpression = unaryExpression;
                }
            }

        }

        return retExpression;
    }

    //positfixExpression -> primaryExpression ('['expression']' | '(' argmentList ')' | '++' | '--') *
    private ASTExpression positfixExpression()
    {
        ASTExpression expression = null;

        ASTExpression primaryExpression = primaryExpression();
        expression = primaryExpression;
        nextToken = tknList.get(tokenIndex);


        if(nextToken.type.equals("'['"))
        {
            ASTExpression arrayAccess = arrayAccess(primaryExpression);
            expression = arrayAccess;
        }
        else if(nextToken.type.equals("'('"))
        {
            ASTExpression funCall = functionCall(primaryExpression);
            expression = funCall;
        }


        nextToken = tknList.get(tokenIndex);
        if(nextToken.type.equals("'++'") || nextToken.type.equals("'--'") )
        {
            ASTToken op = transformNextToken();

            ASTPostfixExpression postfixExpression = new ASTPostfixExpression();
            postfixExpression.expr = expression;
            postfixExpression.children.add(expression);
            postfixExpression.op = op;
            postfixExpression.children.add(op);

            expression = postfixExpression;
        }
        return expression;
    }


    //primaryExpression -> Identifier | constant | '(' expression ')' | castExpression
    private ASTExpression primaryExpression()
    {
        ASTExpression retExpression = null;
        //primaryExpression
        nextToken = tknList.get(tokenIndex);
        if(Identifier.contains(nextToken.type)) //Identifier
        {
            ASTIdentifier id = identifier();
            retExpression = id;
        }
        //常量
        else if(constant.contains(nextToken.type) || stringLiteral.contains(nextToken.type))    //constants
        {
            if(nextToken.type.equals("IntegerConstant"))
            {
                ASTIntegerConstant intConstant = new ASTIntegerConstant();
                intConstant.value = Integer.parseInt(nextToken.lexme);
                intConstant.tokenId = tokenIndex;
                tokenIndex++;

                retExpression = intConstant;
                ASTActualValue astActualValue = new ASTActualValue(intConstant.value.toString());
                retExpression.children.add(astActualValue);
            }
            else if(nextToken.type.equals("FloatingConstant"))
            {
                ASTFloatConstant floatConstant = new ASTFloatConstant();
                floatConstant.value = Double.parseDouble(nextToken.lexme);
                floatConstant.tokenId = tokenIndex;
                tokenIndex++;
                retExpression = floatConstant;
                ASTActualValue astActualValue = new ASTActualValue(floatConstant.value.toString());
                retExpression.children.add(astActualValue);
            }
            else if(nextToken.type.equals("CharacterConstant"))
            {
                ASTCharConstant charConstant = new ASTCharConstant();
                charConstant.value = nextToken.lexme;
                charConstant.tokenId = tokenIndex;
                tokenIndex++;
                retExpression = charConstant;

                ASTActualValue astActualValue = new ASTActualValue(charConstant.value);
                retExpression.children.add(astActualValue);

            }
            else if(nextToken.type.equals("StringLiteral"))
            {
                ASTStringConstant stringConstant = new ASTStringConstant();
                stringConstant.value = nextToken.lexme;
                stringConstant.tokenId = tokenIndex;
                tokenIndex++;
                retExpression = stringConstant;

                ASTActualValue astActualValue = new ASTActualValue(stringConstant.value);
                retExpression.children.add(astActualValue);
            }
        }
        return retExpression;
    }

    //arrayAccess -> '[' expression ']' (arrayAccess | postfix)
    private ASTExpression arrayAccess(ASTExpression arrayName)
    {
        ASTArrayAccess arrayAccess = new ASTArrayAccess();
        nextToken = tknList.get(tokenIndex);
        if(nextToken.type.equals("'['"))
        {

            matchToken("'['");
            ArrayList<ASTExpression> elements = arrayElements();
            arrayAccess.elements.addAll(elements);
            arrayAccess.children.addAll(elements);
            matchToken("']'");
            arrayAccess.arrayName = arrayName;
            arrayAccess.children.add(arrayName);
            return arrayAccess(arrayAccess);
        }
        else
            return arrayName;
    }

    //funCall -> '(' argList ')'
    private ASTFunctionCall functionCall(ASTExpression funcName)
    {
        matchToken("'('");
        ASTFunctionCall functionCall = new ASTFunctionCall();
        functionCall.funcname = funcName;
        functionCall.children.add(funcName);
        nextToken = tknList.get(tokenIndex);
        if(!nextToken.type.equals("')'")) {
            ArrayList<ASTExpression> elements = arrayElements();
            functionCall.argList.addAll(elements);
            functionCall.children.addAll(elements);
        }
        matchToken("')'");
        return functionCall;
    }

    //arrayElements -> exp ',' arrayElements | exp
    private ArrayList<ASTExpression> arrayElements()
    {
        ArrayList<ASTExpression> elements = new ArrayList<>();
        ASTExpression expression = expression();
        elements.add(expression);
        nextToken = tknList.get(tokenIndex);
        if(nextToken.type.equals("','"))
        {
            matchToken("','");
            ArrayList<ASTExpression> elements1 = arrayElements();
            elements.addAll(elements1);
        }
        return elements;
    }

    // returnStatement -> 'return' exprs ';' | 'return' ';'
    private ASTReturnStatement returnStatement()
    {
        matchToken("'return'");
        nextToken = tknList.get(tokenIndex);
        ASTReturnStatement returnStatement = new ASTReturnStatement();
        if(!nextToken.type.equals("';'")) {
            ArrayList<ASTExpression> expressions = expressionList();
            if (expressions != null) {
                returnStatement.expr.addAll(expressions);
                returnStatement.children.addAll(expressions);
            }
            else
                returnStatement.expr = null;
        }
        else {
            returnStatement.expr = null;
        }
        return returnStatement;
    }

    //selectionStatement -> 'if' '(' expression ')' statement
    //                      | 'if' '(' expression ')' statement 'else' statement
    private ASTSelectionStatement selectionStatement()
    {
        ASTSelectionStatement selectionStatement = new ASTSelectionStatement();
        nextToken = tknList.get(tokenIndex);
        if(nextToken.type.equals("'if'")) {
            matchToken("'if'");
            matchToken("'('");
            ASTExpression condition = expression();
            selectionStatement.cond.add(condition);
            selectionStatement.children.add(condition);
            matchToken("')'");
            ASTNode thenStatement = statement();
            selectionStatement.then = thenStatement;    //这里将 then 改为 ASTNode
            selectionStatement.children.add(thenStatement);

            nextToken = tknList.get(tokenIndex);
            if (nextToken.type.equals("'else'")) {
                matchToken("'else'");
                ASTNode otherStatement = statement();
                selectionStatement.otherwise = otherStatement;
                selectionStatement.children.add(otherStatement);
            }
        }
        return selectionStatement;
    }

    //
    private ASTStatement iterationStatement()
    {
        ASTStatement iterationStat = null;
        nextToken = tknList.get(tokenIndex);
        if(nextToken.type.equals("'while'"))
        {
            matchToken("'while'");
            matchToken("'('");
            ASTIterationStatement iterationStatement = new ASTIterationStatement();
            ASTExpression cond = expression();
            iterationStatement.cond.add(cond);
            iterationStatement.children.add(cond);
            matchToken("')'");
            ASTNode statement = statement();
            iterationStatement.stat = statement;
            iterationStatement.children.add(statement);
            iterationStat = iterationStatement;
        }
        else if(nextToken.type.equals("'for'"))
        {
            matchToken("'for'");
            matchToken("'('");
            nextToken = tknList.get(tokenIndex);
            if(typeKeys.contains(nextToken.type))   //有申明的情况
            {
                ASTIterationDeclaredStatement iterationDeclaredStatement = new ASTIterationDeclaredStatement();
                ASTDeclaration declaration = localDeclaration();
                iterationDeclaredStatement.init = declaration;
                iterationDeclaredStatement.children.add(declaration);
                matchToken("';'");
                nextToken = tknList.get(tokenIndex);
                if(!nextToken.type.equals("';'")) {
                    ASTExpression cond = expression();
                    iterationDeclaredStatement.cond.add(cond);
                    iterationDeclaredStatement.children.add(cond);
                }
                matchToken("';'");
                nextToken = tknList.get(tokenIndex);
                if(!nextToken.type.equals("')'")) {
                    ASTExpression stem = expression();
                    iterationDeclaredStatement.step.add(stem);
                    iterationDeclaredStatement.children.add(stem);
                }
                matchToken("')'");
                ASTNode stat = statement();
                iterationDeclaredStatement.stat = stat;
                iterationDeclaredStatement.children.add(stat);
                iterationStat = iterationDeclaredStatement;
            }
            else
            {
                ASTIterationStatement iterationStatement = new ASTIterationStatement();
                nextToken = tknList.get(tokenIndex);
                if(!nextToken.type.equals("';'")) {
                    ASTExpression init = expression();
                    iterationStatement.init.add(init);
                    iterationStatement.children.add(init);
                }
                matchToken("';'");
                nextToken = tknList.get(tokenIndex);
                if(!nextToken.type.equals("';'")) {
                    ASTExpression cond = expression();
                    iterationStatement.cond.add(cond);
                    iterationStatement.children.add(cond);
                }
                matchToken("';'");
                nextToken = tknList.get(tokenIndex);
                if(!nextToken.type.equals("')'")) {
                    ASTExpression stem = expression();
                    iterationStatement.step.add(stem);
                    iterationStatement.children.add(stem);
                }
                matchToken("')'");
                ASTNode stat = statement();
                iterationStatement.stat = stat;
                iterationStatement.children.add(stat);
                iterationStat = iterationStatement;
            }
        }
        return iterationStat;
    }

    //jumpStatement -> ('break' | 'continue') ';' | 'goto' Identifier ';'
    private ASTStatement jumpStatement()
    {
        ASTStatement jumpstatement = null;
        nextToken = tknList.get(tokenIndex);
        if(nextToken.type.equals("'break'"))
        {
            matchToken("'break'");
            ASTBreakStatement breakStatement = new ASTBreakStatement();
            jumpstatement = breakStatement;
        }
        else if(nextToken.type.equals("'continue'"))
        {
            matchToken("'continue'");
            ASTContinueStatement continueStatement = new ASTContinueStatement();
            jumpstatement = continueStatement;
        }
        else if(nextToken.type.equals("'goto'"))
        {
            matchToken("'goto'");
            ASTGotoStatement gotoStatement = new ASTGotoStatement();
            gotoStatement.label = identifier();
            jumpstatement = gotoStatement;
        }
        return jumpstatement;
    }

    //typeSpecifiers -> typeKey*
    private ArrayList<ASTToken> typeSpecifiers()
    {
        ArrayList<ASTToken> sps = new ArrayList<>();
        ASTToken sp = transformNextToken();
        sps.add(sp);
        nextToken = tknList.get(tokenIndex);
        while(typeKeys.contains(nextToken.type) || pointer.contains(nextToken.type))
        {
            ASTToken token = transformNextToken();
            sps.add(token);
            nextToken = tknList.get(tokenIndex);
        }
        return sps;
    }

    //identifier
    private ASTIdentifier identifier()
    {
        ASTIdentifier id = new ASTIdentifier();
        ASTActualValue value = new ASTActualValue();
        nextToken = tknList.get(tokenIndex);
        if(Identifier.contains(nextToken.type))
        {
            id.tokenId = tokenIndex;
            id.value = nextToken.lexme;
            tokenIndex++;
            value.value = nextToken.lexme;
            id.children.add(value);
        }
        else{
            matchToken("'Identifier'");
        }
        return id;
    }

    //matchToken
    private ASTToken transformNextToken()
    {
        ASTToken token = new ASTToken();
        ASTActualValue value = new ASTActualValue();
        nextToken = tknList.get(tokenIndex);
        if(nextToken != null) {
            token.tokenId = tokenIndex;
            token.value = nextToken.lexme;
            value.value = nextToken.lexme;
            token.children.add(value);
        }
        tokenIndex++;
        return token;
    }
}
